package com.note.leetcode;


/**
 * @ClassName 平衡二叉树
 * @Description TODO
 * @Author QiBin
 * @Date 2020/6/1411:15
 * @Version 1.0
 * //给定一个二叉树，判断它是否是高度平衡的二叉树。
 * //
 * // 本题中，一棵高度平衡二叉树定义为：
 * // 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
 * // 示例 1:
 * //
 * // 给定二叉树 [3,9,20,null,null,15,7]
 * //
 * //     3
 * //   / \
 * //  9  20
 * //    /  \
 * //   15   7
 * //
 * // 返回 true 。
 * //
 * //示例 2:
 * //
 * // 给定二叉树 [1,2,2,3,3,null,null,4,4]
 * //
 * //        1
 * //      / \
 * //     2   2
 * //    / \
 * //   3   3
 * //  / \
 * // 4   4
 * //
 * //
 * // 返回 false 。
 * //
 * //
 * // Related Topics 树 深度优先搜索
 *
 **/
public class 平衡二叉树 {


    public static void main(String[] args) {



    }

    // Recursively obtain the height of a tree. An empty tree has -1 height
    private int height(Node root) {
        // An empty tree has height -1
        if (root == null) {
            return -1;
        }
        return 1 + Math.max(height(root.getLeft()), height(root.getRight()));
    }

    public boolean isBalanced(Node root) {
        // An empty tree satisfies the definition of a balanced tree
        if (root == null) {
            return true;
        }

        // Check if subtrees have height within 1. If they do, check if the
        // subtrees are balanced
        return Math.abs(height(root.getLeft()) - height(root.getRight())) < 2
                && isBalanced(root.getLeft())
                && isBalanced(root.getRight());
    }
    final class TreeInfo {
        public final int height;
        public final boolean balanced;

        public TreeInfo(int height, boolean balanced) {
            this.height = height;
            this.balanced = balanced;
        }
    }

    /**
     * =================
     */
    class Solution {
        // Return whether or not the tree at root is balanced while also storing
        // the tree's height in a reference variable.
        private TreeInfo isBalancedTreeHelper(Node root) {
            // An empty tree is balanced and has height = -1
            if (root == null) {
                return new TreeInfo(-1, true);
            }

            // Check subtrees to see if they are balanced.
            TreeInfo left = isBalancedTreeHelper(root.getLeft());
            if (!left.balanced) {
                return new TreeInfo(-1, false);
            }
            TreeInfo right = isBalancedTreeHelper(root.getRight());
            if (!right.balanced) {
                return new TreeInfo(-1, false);
            }

            // Use the height obtained from the recursive calls to
            // determine if the current node is also balanced.
            if (Math.abs(left.height - right.height) < 2) {
                return new TreeInfo(Math.max(left.height, right.height) + 1, true);
            }
            return new TreeInfo(-1, false);
        }

        public boolean isBalanced(Node root) {
            return isBalancedTreeHelper(root).balanced;
        }

    }
}
